Many automated digital communication processes employ convolutional coding, as for example a means of forward error correction and/or for other purposes. Such correction can be used, for example, to make signal communication robust against undesired disturbances like noise and other signal errors.
In digital telecommunications processes, a signal to be transmitted from one terminal to another can be convolutionally encoded prior to transmission. Upon reception, the convolutionally encoded signal is typically decoded prior to further processing. Many methods of convolutionally encoding and decoding telecommunications signals using suitably-configured and -programmed data processors are known. Many such methods involve the application of the so-called Viterbi algorithm.
For example, using “register exchange” methods, Viterbi survivor paths can be stored using registers and multiplexers. In such approaches desirable numbers and configurations of connections of registers and multiplexers may be derived from a corresponding Viterbi trellis diagram, the characteristics of which in turn depend on the characteristics of generator polynomials used in the convolutional encoder, which in turn can depend upon the required robustness of the channel coding against noise and other signal disturbances, and the expected bit length of data strings to be processed.
Data records of various string lengths can be used for different purposes. For example, control signals can be employed on dedicated control channels, and can be of different bit length than content signals carried on content channels. Common lengths for control signal data records for systems currently in common use, for example for the Long Term Evolution (LTE) standard, can vary from 25 to 70 bits.
Such a register exchange process requires an array of L×N registers, where:                L=the bit length of the data strings to be processedN=2M=2(CL-1)=number of Trellis states        CL=the constraint length of the convolutional encoder        M=CL−1=number of delay elements of the convolutional encoderThe constraint length is a measure for the memory depth of the coding. It corresponds to the number of delay elements M of the convolutional encoder, plus 1. The larger the constraint length, the stronger is the protection of the information sequence to be transmitted against noise and other signal disturbances. But as the decoding complexity increases strongly (approximately quadratically) for larger constraint lengths, the practical implementation gives a strong upper bond for this value. In common current communication standards the constraint length CL is approximately 6 to 8 (e.g., for LTE, CL=7). One disadvantage of the register exchange approach is that during execution of the trellis search, simultaneous read and write access to all L×N registers is required at all times, with resultant high power consumption requirements, and corresponding short battery life in mobile systems.        
As is known to those skilled in the relevant arts, “registers” suitable for use in implementing processes according to the disclosure include buffers and/or other memory(ies) immediately accessible by a processor for read and store operations. In the Application Specific Integrated Circuit (ASIC) context, one register is normally equivalent to twelve NAND gates.
Another approach to the decoding of Viterbi-encoded data has been the trace-back approach. In this type approach only N decision bits need be stored in each time step, and random access memory (RAM) can be used. However, when the trellis search has been completed, the optimal path through the trellis must be determined by applying a trace-back algorithm. This produces inverse-ordered output data, which must be processed using a last-in-first-out (LIFO) unit in order to invert the decoded output sequence. This increases latency time in processing, with resultant effects on signal and communications quality such as, for example, the ACK/NACK (Acknowledge, Non-Acknowledge) response time of a communication system. In the context of control channel information decoding, latency can be very critical, as very often the User Equipment (UE) only has to check if the base station has a message for it and if not the UE can go directly into sleep mode. The faster the control decoding can be done, the faster the decision can be made to go into sleep mode to save power, which is crucial for mobile communication devices.
In view of the several disadvantages to these approaches, hybrid techniques have been proposed. An example of such hybrid processes is the “Modified Register Exchange” (MRE) method described by Han, Kim, and Lee in ISCAS, IEEE 2004. The MRE approach divides a RAM used for storage of trellis data into Q sub-blocks, where Q depends on the desired latency for the decoding. The larger the chosen value for Q, the lower the overall decoding latency. In this type approach, Q−1 trace-forward units, each comprising an (N×M)-bit register, are required in order to track the intermediate state addresses of all N possible survivor paths at the end of each sub-block, where M is the bit width, in binary format, which is required to track N different states. Therefore,M=log2N=log2(2CL-1)=CL−1
After the trellis search is completed, only a partial trace-back (a “sub-trace-back”) is needed before the first decoded data sequence can be output in non-inverse order. This approach reduces the latency imposed by the pure trace-back approach, but the complexity of the processing architecture is increased, along with memory, and therefore power consumption requirements, with an inverse effect on battery life where applicable.
Thus it may be seen that the extreme efficiency requirements imposed by, for example, the need for efficient use of finite bandwidths available for the processing of large amounts of rapid signal traffic, and the limited amount of power available in battery-driven devices, mean that significant advantages stand to be gained from the optimization of systems, architectures, and methods of processing convolutionally encoded communications data streams.
As noted above, Viterbi and other convolutional coding processes suitable for use in processing streams of telecommunications data using systems and processes disclosed herein are known to those skilled in the relevant arts. Although they have not previously been modified or implemented in the manner described herein, basics of methods and processes suitable for use in decoding convolutionally encoded streams of such data, including, for example, basic trellis search processes, trace-forward processes, trace-back processes, and tail-biting processes, are also known to those skilled in the relevant arts.
Similar reference numerals may have been used in different figures to denote similar components.